package com.backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Solution10 {
    List<String> res = new ArrayList<>();


    LinkedList<String> tmp = new LinkedList<>();
    public List<String> restoreIpAddresses(String s) {
        backTracking(s,0);
        return res;
    }


    public void backTracking(String s, int index) {
        if (tmp.size()== 4) {
            if (index == s.length()) {
                StringBuilder stringBuilder = new StringBuilder();
                for (int i = 0; i < tmp.size(); i++) {
                    stringBuilder.append('.').append(tmp.get(i));
                }
                stringBuilder.deleteCharAt(0);
                res.add(stringBuilder.toString());
            }
            return;
        }
        for (int i = index; i < s.length(); i++) {
            if (isValid(s,index,i)) {
                tmp.add(s.substring(index,i+1));
                backTracking(s,i+1);
                tmp.removeLast();
            } else break;
        }
    }

    public boolean isValid(String str, int start, int end) {
        if (start > end) {
            return false;
        }
        if (start != end && str.charAt(start) == '0') return false;
        int num = 0;
        for (int i = start; i < end+1; i++) {
            num = 10*num+(str.charAt(i)-'0');
            if (num > 255 ) return false;
        }
        return true;
    }

}
